package com.cute.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class ZhongXuBianLiDeXiaYiGeJieDian {

    /**
     * 给定一棵二叉树，找出目标节点的中序遍历的下一个节点
     * 分析：
     *      1.如果当前节点有右子树，那么当前节点的下一个节点一定是右子树的最左子节点
     *      2.如果当前节点没有右子树，且当前节点是父节点的左子节点，那么下一个节点就是当前节点的父节点
     *      3.如果当前节点没有右子树，且当前节点是父节点的右子节点，
     *          那就下一个节点就需要从当前节点的父节点向上找直到存在最近的根节点的左子节点是父节点
     *      4.如果当前节点没有右子树，且是父节点的右子节点，且想上找时不存在3中存在的根节点，那么当前节点
     *          没有下一个节点
     */
    public static void main(String[] args) {
        int val = 154;
        TreeNode root = new TreeNode(1);
        Stack<TreeNode> stack = new Stack<>();
        int res = Integer.MAX_VALUE;
        while (!stack.isEmpty() || root != null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else {
                TreeNode temp = stack.pop();
                if (temp.val == val){
                    if (temp.right != null) res = temp.right.val;
                    else if (stack.peek() != null) res = stack.pop().val;
                    break;
                }
                else root = temp.right;
            }
        }
        if (res == Integer.MAX_VALUE) System.out.println("不存在下一个");
        else System.out.println(res);
    }

    /**
     * 直接根据目标节点去寻找中序遍历的下一个节点
     * 分析：
     *      1.如果当前节点有右子树，那么当前节点的下一个节点一定是右子树的最左子节点
     *      2.如果当前节点没有右子树，且当前节点是父节点的左子节点，那么下一个节点就是当前节点的父节点
     *      3.如果当前节点没有右子树，且当前节点是父节点的右子节点，
     *          那就下一个节点就需要从当前节点的父节点向上找直到存在最近的根节点的左子节点是父节点
     *      4.如果当前节点没有右子树，且是父节点的右子节点，且想上找时不存在3中存在的根节点，那么当前节点
     *          没有下一个节点
     */
    public TreeNode findNext(TreeNode target){
        if (target == null) return null;
        TreeNode res = null;
        if (target.right != null){//当前节点的右子树不为空
            target = target.right;
            while (target.left != null) target = target.left;
            res = target;
        }else if (target == target.parent.left){//右子树为空但是当前节点是父节点的左子节点
            res = target.parent;
        }else {//右子树为空且为父节点的右子节点
            while (target.parent != null && target != target.parent.left) target = target.parent;
            if (target.parent != null) res = target;
        }
        return res;
    }

    /**
     * 此二叉树除左右子树外，还有父节点
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        TreeNode(int x) { val = x; }
    }
}
